In recent years, as the information-intensive society is developed and the semiconductor technique makes advance, the improvement of reliability of digital data becomes more important. When digital data are tried to be transmitted or recorded accurately, transmission data are influenced by noises or the like in a transmission channel to be transmitted improperly, elements are failed, or recording media or the like are defected, and thus it is necessary to detect and correct errors which occurred due to them. In order to realize the detection and correction of the errors, various error correction and detection codes have been developed on the basis of the code theory.
As the conventional error correction codes, for example, a Hong-Patel code which is excellent as a code for correcting any error occurred within a byte (SbEC code) (where, a mass of b bits is called a byte and b is an integer that is 2 or more.) is disclosed (for example, see Non-Patent Document 1).
Further, an odd number weight string byte error correction code including a single-bit error correction and double-bit error detection code, which is conventionally used the most frequently in high-speed semiconductor memory systems, is disclosed (for example, see Non-Patent Document 2).
A code for correcting single-byte error and detecting double-byte error (SbEC-DbED code) is proposed as a Reed-Solomon code and as a code which is obtained by improving the Reed-Solomon code and is efficient, and it has been already utilized in main memory device of many computer systems or the like (for example, see Non-Patent Documents 3 and 4).
Moreover, as a code for detecting byte errors, a code for correcting single-bit error and detecting double-bit error and single-byte error (SEC-DED-SbED code) is made in public, and is currently applied to main memory device of many computer systems, (for example, see Non-Patent Document 5).
The concrete contents of the mutually related code research and development up to the late 1980s are pan optically described in Non-Patent Document 6.
Thereafter, as a code for high-speed semiconductor memory systems which is newly developed, a code for correcting single-byte error and detecting double-bit error (SbEC-DED code) is disclosed in Non-Patent Document 7, and a code for correcting single-byte error and simultaneously detecting single-bit error and single-byte error (SbEC-(S+Sb)ED code) is disclosed in Non-Patent Document 8. Further, a code for correcting single-byte error and also correcting double-bit error if occurred (SbEC-DEC code) is disclosed in Non-Patent Document 9.
Particularly, as a code which is most related to the present invention, an invention relating to an St/bEC code for correcting single-spotty-byte error, and relating to an St/bEC-SbED code for correcting single-spotty-byte error and detecting single-byte error exceeding t bits within a byte is already disclosed (see Patent Document 1). Where, a “spotty-byte error” is a “t/b error”, i.e. errors up to t bits (t≦b) within a byte composed of b bits. Particularly, the St/bEC code is disclosed in Non-Patent Document 10.
Further, an invention relating to an St/bEC-Dt/bED code for correcting single-spotty-byte error and detecting double-spotty-byte error and relating to an St/bEC-Dt/bED-SbED code for correcting single-spotty-byte and detecting both double-spotty-byte errors and single-byte errors exceeding t bits within a byte is already applied (see Patent Document 2).
In the case of considering a plurality of spotty-byte errors, an error in which only single-spotty-byte error occurred within a byte, is called “single spotty-byte error within a byte”. An invention relating to a general constitution method in which a distance “d” is provided to the single spotty-byte error within a byte has been already filed (see Patent Document 3).
Further, an error in which a plurality of spotty-byte errors (namely, two or more spotty-byte errors) occurred within a byte is called “multiple spotty-byte errors within a byte”. An invention relating to a general constitution method in which a distance “d” is provided to the multiple spotty-byte errors within a byte has been already filed (see Patent Document 4).
Since elements which have input-output of 1-bit data are mainly used as semiconductor memory elements until the mid-1980s, single-bit error correction and double-bit error detection code (SEC-DED code) for correcting an error of one element and detecting errors to two elements is used frequently. However, elements having input-output of 4-bit data start to be a mainstream from the mid-1980s according to high integration of memory elements, and thus the S4EC-D4ED code and the SEC-DED-S4ED code whose byte width “b” is 4 bits (b=4) are mainly used. Further, semiconductor memory elements having input-output of 8-bit and 16-bit data start to be a mainstream from the mid-1990s.
However, when the byte width of 8 bits (b=8) or 16 bits (b=16) is applied to the byte width “b” of the conventional SbEC-DbED code, the proportion of the number of check bits share to the total code length is about 30% to 40%, which is large, and the code rate is reduced, thereby arising a practically significantly important problem.
In memory device using these semiconductor memory elements (DRAM elements, herein after, also simply referred to as element), temporary fault occurs due to noises, alpha particles and the like, or the DRAM elements are deteriorated and are not operated, namely, permanent fault occurs. 80% or more of the recent devices using the DRAM elements temporarily faulted, and particularly in the DRAM elements having multi-bit data input-output of 8 or more bits, the most of bit errors are errors of comparatively small bits such as 1, 2 and 3 bit within a byte.
Among them, a temporary error due to electromagnetic noises and alpha particles with comparatively low-level energy and single-bit error due to the permanent fault of a memory cell are generated most frequently. Recently, since mobile devices loaded with the DRAM elements are used so frequently, the use in unsatisfactory electromagnetic environments should be taken into consideration. In the DRAM elements in electronic devices to be used for high-altitude aircrafts and fighting aircrafts, it is highly possible that the temporary fault having about double-bit error or triple-bit error occurs due to collision of neutron particles or the like of high energy level caused by cosmic ray. In the DRAM elements loaded onto space appliances to be used for satellite communication and space communication, it is necessary to consider the heavy damage due to the collision of particles of a high energy level, and in this case, 2 or more bits error should be taken into consideration.
Since the bit error occurrence is widely ranging as mentioned above, the St/bEC-SbED code which can be structured by giving any value to parameters t and b is a very practical code system, when this code is used for the memory device using the DRAM chips of 8 or more bits. That is, the St/bEC-SbED code is provided with the function capable of correcting spotty-byte error, i.e. one chip error up to t bits (t is smaller than the byte width b and the value of t can be arbitrarily determined by designer who conduct a search on tendency of error) and the function capable of detecting single-byte errors exceeding t-bit errors whose probability of occurrence is low. As a result, the St/bEC-SbED code can correct and detect error by using the significantly smaller number of check bits than that of a conventional error control code such as the Reed-Solomon code (RS code) with which errors are controlled by byte unit.
The St/bEC-Dt/bED-SbED code is a very practical code system for an error to extend to two arbitrary chips (the two arbitrary chips is not limited to adjacent two chips), when this code is used in the memory device using the DRAM chips of 8 or more bits. That is, the St/bEC-Dt/bED-SbED code is provided with the function capable of correcting one chip error up to t (t is smaller than the byte width b) bits (single-spotty-byte error correction, St/bEC), the function capable of detecting spotty-byte error to extend to two elements (double-spotty-byte error detection, Dt/bED) and the function capable of detecting single-byte error exceeding t-bits though whose probability of occurrence is low (single-byte error detection, SbED). As a result, the St/bEC-Dt/bED-SbED code can correct and detect bit error by using the significantly smaller number of check bits than that of a conventional code system which correct and detect bit error by byte unit.
A spotty-byte error control code generally having a distanced over GF(2b) is constructed theoretically for the single spotty-byte error within a byte and the multiple spotty-byte errors within a byte, so that an error to extend to two or more chips can be corrected and detected.
However, an error to extend to a lot of chips seldom occurs at the same time. Generally, an error occurs in a limited number of elements, namely, in a limited number of bytes. In addition, the number of chips on which an error occurs is two or three at most.
The present invention is devised in view of the above circumstances, and it is an object of the present invention to provide a method and an apparatus for correcting and detecting multiple spotty-byte errors within a byte occurred in a limited number of bytes.
It is another object of the present invention to provide a method and an apparatus for correcting and detecting multiple spotty-byte errors within a byte occurred in a limited number of bytes with controlling random bit errors occurred in the limited number of bytes when t=1.
Further, it is still another object of the present invention to provide a method and an apparatus for correcting and detecting multiple spotty-byte errors within a byte occurred in a limited number of bytes with detecting single byte errors exceeding correction capability of multiple spotty-byte errors within a byte whose probability of occurrence is low.